from chapter7.TreeNode import TreeNode

class binary_search_tree(self):
    def search(self, num):
        cur = self._root
        while cur is not None:
            if cur.val < num:
                cur = cur.right
            elif cur.val > num:
                cur = cur.left
            else:
                break
        return cur

    # 注意二叉搜索树不允许存在重复节点，否则将违反其定义，因此，若将插入节点在树中已存在，则不执行插入，直接返回
    # 为了实现插入，需要借助节点pre保存上一轮循环的节点，这样在遍历至None时，可以获取到父节点，从而完成节点插入操作
    def insert(self, num):
        if self._root is None:
            self._root = TreeNode(num)
            return
        cur, pre = self._root, None
        while cur is not None:
            if cur.val == num:
                return
            pre = cur
            if cur.val < num:
                cur = cur.right
            else:
                cur = cur.left
        node = TreeNode(num)
        if pre.val < num:
            pre.right = node
        else:
            pre.left = node

    # 删除节点，需要先在二叉树中查找到目标节点，再将其删除，我们需要保证在删除操作完成后，二叉搜索树的“左子树<根节点<右子树”的性质仍然满足
    # 因此根据目标节点的子节点数量，分0/1和2三种情况，执行对应的删除节点操作。
    def remove(self, num):
        if self._root is None:
            return
        cur, pre = self._root, None
        while cur is not None:
            if cur.val == num:
                break
            pre = cur
            if cur.val < num:
                cur = cur.right
            else:
                cur = cur.left
        if cur is None:
            return

        if cur.left is None or cur.right is None:
            child = cur.left or cur.right
            if cur != self._root:
                if pre.left == cur:
                    pre.left = child
                else:
                    pre.right = child
            else:
                self._root = child
        else:
            tmp = cur.right
            while tmp.left is not None:
                tmp = tmp.left
            self.remove(tmp.val)
            cur.val = tmp.val
    # 中序遍历需要遵循左-根-右的遍历顺序，而二叉搜索树满足左子节点<根节点<右子节点的大小关系
    # 这意味着在二叉搜索树中进行中序遍历时，总会优先遍历下一个最小节点，从而得到一个重要性质：二叉搜索树中的中序遍历序列是升序的
    # 在理想状态下，二叉搜索树是平衡的，这样就可以在logn轮循环内查找任意节点，然而如果我们在二叉搜索树中不断插入和删除节点，可能导致二叉树退化为链表，其复杂度也会退化为O(n)